package leetcode;

/**
 * 547. 省份数量    https://leetcode.cn/problems/number-of-provinces/description/
 * 并查集：解决连通性
 */
public class LeetCode547 {

    public static int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.sets;
    }

    static class UnionFind {
        // 节点的向上节点
        public int[] parent;
        // 向上节点区域的数量（用于小区域加入大区域的判断）
        public int[] size;
        // 辅助数组，用于做向上查找链表优化,用数组代替栈
        public int[] help;
        // 区域数量
        public int sets;

        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            help = new int[n];
            sets = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        // 查找向上节点
        public int find(int node) {
            int cur = node;
            int index = 0;
            while (cur != parent[cur]) {
                help[index++] = cur;
                cur = parent[cur];
            }
            size[cur] += index;
            for (--index; index >= 0; index--) {
                parent[help[index]] = cur;
            }
            return cur;
        }

        // 合并两个区域
        public void union(int a, int b) {
            int node1 = find(a);
            int node2 = find(b);
            if (node1 != node2) {
                if (size[node1] >= size[node2]) {
                    parent[node2] = node1;
                    size[node1] += size[node2];
                } else {
                    parent[node1] = node2;
                    size[node2] += size[node1];
                }
                sets--;
            }
        }
    }
}
